/**Author: 		Andrew Shore
 * Class:  		CSCE 146 Section 005
 * Date:   		3-19-09 
 * Assignment:	Homework 04: Heap, Priority Queue
 */
import java.util.ArrayList;
import java.util.Scanner;


public class PQ implements IPQ {
	String classLabel="PQ:";
	private int size;
	private ArrayList<ProcessRecord> list;
	
	
	
	public PQ(){
		Scanner inFile=null;
		ProcessRecord rec=null;
		inFile=FileUtils.ScannerOpen("zin");
		FileUtils.setLogFile("zlog");
		size=0;
		this.list=new ArrayList<ProcessRecord>();
		
	}
	
	public void setList(ArrayList<ProcessRecord> list) {
		this.list = list;
	}
	public ArrayList<ProcessRecord> getList() {
		return list;
	}
	
	@Override
	public int getSize() {
	// TODO Auto-generated method stub
		return list.size();
	}
	
	/*Starts at the element of index 'which' and sorts the tree going down by swaping the parent with
	 * the larger of the two children until it is sorted correctly, used in remove method(where which=0)
	 * 
	 */
	@Override
	public void fixHeapDown(int which) {
		// TODO Auto-generated method stub
		
		boolean isGreater=true;			//stops loop if the parent is greater than both children
		//while parent has at least one child and is smaller than one of the children
		while(which*2+1<list.size()-1 && isGreater){
			int leftChild=2*which+1;		//index of left child
			int rightChild=2*which+2;		//index of right child
			int rightPri=list.get(rightChild).getPriority();		//priority of right child
			int leftPri=list.get(leftChild).getPriority();			//priority of left child
			
			//if one of the children's priority is greater than the parents
			if(rightPri >list.get(which).getPriority() || 
					leftPri>list.get(which).getPriority()){
				//if the left priority is greater than it is swapped with parent else right is swapped
				if(leftPri>rightPri){
					ProcessRecord temp=list.get(which);
					list.set(which, list.get(leftChild));
					list.set(leftChild, temp);
					which=leftChild;
				}
				else{
					ProcessRecord temp=list.get(which);
					list.set(which, list.get(rightChild));
					list.set(rightChild, temp);
					which=rightChild;
					
				}
				
			}
			//heap is sorted
			else{
				isGreater=false;
			}
		}
	}		
	/*	Starts at the element with index 'which' and sorts the heap going up switching the element with its 
	 * parent if it's priority is higher, used in insert method(where which=the size of the array-1)
	 */
	@Override
	public void fixHeapUp(int which) {
		// TODO Auto-generated method stub
		boolean isLessThan=true;		//if the child is less than parent then heap is sorted
		
		//while the element is not the root of the tree and the child is less than the parent
		while(which!=0 && isLessThan){
			
			int parent=(which-1)/2;			//calculates index of parent
			
				//swaps parent and child if they are out of order
				if(list.get(parent).getPriority() <list.get(which).getPriority()){
						
					ProcessRecord temp=list.get(which);
					list.set(which, list.get(parent));
					list.set(parent, temp);
					which=parent;
			}
			else{
				isLessThan=false;
			}
		}
	}


	@Override
	public void insert(ProcessRecord newRecord) {
		// TODO Auto-generated method stub
		this.list.add(newRecord);
		//sorts the heap starting at the record that was just added
		this.fixHeapUp(list.size()-1);
	}

	@Override
	public ProcessRecord removeMax() {
		
		// TODO Auto-generated method stub
		ProcessRecord max=list.get(0);
		FileUtils.logFile.println(classLabel+" Got item' "+ max.toString());
		//takes the last element of the tree and puts it into the root position, thus removing the root
		FileUtils.logFile.println(classLabel+" Swap with' "+ list.get((list.size()-1)));
		list.set(0, list.get((list.size()-1)));
		FileUtils.logFile.println(classLabel+" Swapped values");
		//removes last element of the tree because it was moved to front
		list.remove(list.size()-1);
		FileUtils.logFile.println(classLabel+" did removal"+ this.toString());
		//sorts the heap starting from the root
		this.fixHeapDown(0);
		FileUtils.logFile.println("\n"+classLabel+" The new heap is: "+ this.toString());
		FileUtils.logFile.flush();
		return max;
	}

	@Override
	public ProcessRecord returnMax() {
			return list.get(0);
		}
	public String toString(){
		 String s = "";

		    if(0 == this.getSize())
		    {
		      s = String.format("%nFile is empty.");
		    }
		    else
		    {
		      for(int i = 0; i < this.getSize(); ++i)
		      {
		        s += String.format("%nsubscript %d %s",
		                           i, list.get(i).toString());
		      }
		    }

		    return s;
	}
	public boolean checkHeap(){
		for(int i=0; i<list.size()-1; i++){
			if(2*i+1<list.size()-1){
			if(list.get(i).getPriority()<list.get(2*i+1).getPriority() || 
					list.get(i).getPriority()<list.get(2*i+1).getPriority()){
				return false;
			}
			}
		}
		return true;
	}


}